package com.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * @Description:给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
 * 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
 * 你返回所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 * @Auther: liuyanhui
 * @Date: 2024/03/13/ 10:53
 */
public class ThreeSum {
    public static void main(String[] args) {
        int[] nums = new int[]{-2, 0, 0, 2, 2};
        ThreeSum threeSum = new ThreeSum();
        threeSum.threeSum(nums);

//        int len = nums.length;
//        if(len <3){
//            return;
//        }
//        Arrays.sort(nums);
//        for (int i = 0; i < nums.length - 2; i++) {
//            if(i>0 && nums[i] == nums[i-1]){
//                continue;
//            }
//            int j = i+1;
//            int k = len -1;
//            while(j < k){
//                int sum = nums[i] + nums[j] + nums[k];
//                if(sum == 0){
//                    System.out.println(nums[i] + " " + nums[j] + " " + nums[k]);
//                    k--;
//                    j++;
//                }else if(sum < 0){
//                    j++;
//                }else{
//                    k--;
//                }
//            }
//        }
    }

    // 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
    // * 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
    // * 你返回所有和为 0 且不重复的三元组。
    // * 注意：答案中不可以包含重复的三元组。
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int len = nums.length;
        if (len < 3) {
            return ans;
        }
        Set<String> set = new HashSet<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            int j = i + 1;
            int k = len - 1;
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
//                    System.out.println(nums[i] + " " + nums[j] + " " + nums[k]);
//                    ans.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    set.add(nums[i] + " " + nums[j] + " " + nums[k]);
                    j++;
                    k--;
                } else if (sum < 0) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        if (set.size() > 0) {
            for (String str : set) {
                String[] arr = str.split(" ");
                ans.add(Arrays.asList(Integer.parseInt(arr[0]), Integer.parseInt(arr[1]), Integer.parseInt(arr[2])));
            }
        }
        return ans;
    }

    /**
     * 摩尔投票算法
     *
     * @Description:给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于  n/2 的元素
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     * @Auther: liuyanhui
     * @Date: 2024/3/13 15:17
     */
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = 0;
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                candidate = nums[i];
            }
            count += nums[i] == candidate ? 1 : -1;
        }
        int mumc = 0;
        for (int num : nums) {
            if (num == candidate) {
                mumc++;
            }
        }
        return mumc > nums.length / 2 ? candidate : -1;
    }

    // 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
    // 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0) {
                nums[i] = len + 1;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (index < nums.length && nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }

    // 给你一个链表的头节点 head ，判断链表中是否有环。
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (slow != fast) {
            if(fast == null || fast.next == null){
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }
    // 给你一个链表数组，每个链表都已经按升序排列。
    //请你将所有链表合并到一个升序链表中，返回合并后的链表。
    public ListNode mergeKLists(ListNode[] lists) {
        // 新链表的头结点
        ListNode node = new ListNode(0);
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        for (ListNode list : lists) {
            if(null != list){
                minHeap.offer(list);
            }
        }
        ListNode currentNode = node;
        while(!minHeap.isEmpty()){
            ListNode minNode = minHeap.poll();
            currentNode.next = minNode;
            currentNode = currentNode.next;
            if (minNode.next != null) {
                minHeap.offer(minNode.next);
            }
        }
        return node.next;
    }
}
